/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LXW
 * Date: 2022-01-16
 * Time: 11:18
 */
class ListNode {
    public int val;
    public ListNode next;

    public ListNode (int val) {
        this.val = val;
    }
}
public class Test {
    // 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。力扣203题
    ListNode head;
    public ListNode removeElements (ListNode head,int val) {
        if (head == null) {
            return null;
        }
        ListNode cur = this.head.next;
        ListNode prev = this.head;
        while (cur != null) {
            if (cur.val == val) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        if (head.val == val) {
            head = head.next;
            return head;
        }
        return head;
    }
    // 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。力扣206题
    public ListNode reverse(ListNode head) {
        if (head == null) {
         return null;
        }
        ListNode cur = head.next;
        ListNode curNext = head.next;
        ListNode prev = head;
        while (cur != null) {
            cur.next = prev;
            prev = cur;
            cur = curNext.next;
            curNext = cur;
        }
        return prev;
    }
    // 给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。力扣876题
    public ListNode middleNode (ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {   // 奇数时满足第一个条件，偶数时满足第二个条件
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    // 输入一个链表，输出该链表中倒数第k个结点。
    public ListNode FindKthToTail(int k) {
        if (k < 0 || head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (k-1 != 0) {
            fast = fast.next;
            if (fast == null) {
                return null;
            }
            k--;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
    // 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
    public ListNode mergeTwoLists (ListNode list1, ListNode list2) {
        ListNode node = new ListNode(-1);
        ListNode newHead = node;
        ListNode cur = newHead;
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val){
                cur.next = list1;
                cur = list1;
                list1 = list1.next;
            }else {
                cur.next = list2;
                cur = list2;
                list2 = list2.next;
            }
        }
        if (list1 != null) {
            cur.next = list1;
        }
        if (list2 != null) {
            cur.next = list2;
        }
        return newHead.next;
    }
    // 现有一链表的头指针 ListNode* head，给一定值x，
    // 编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
    public ListNode partition(ListNode head, int x) {
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        while (head != null) {
            if (head.val < x) {
                if (bs == null) {     // 第一次
                    bs = head;
                    be = head;
                }else {              // 不是第一次
                    be.next = head;
                    be = be.next;
                }
            }else {
                if (as == null) {    // 第一次
                    as = head;
                    ae = head;
                }else {             // 不是第一次
                    ae.next = head;
                    ae = ae.next;
                }
            }
            head = head.next;
        }
        // 预防第一个段为空
        if (bs == null) {
            return as;
        }
        be.next = as;
        //预防第2个段当中的数据，最后一个节点不是空的
        if (as != null) {
            ae.next = null;
        }
        return bs;
    }
    // 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
    // 例如，链表 1->2->3->3->4->4->5  处理后为 1->2->5
    public ListNode deleteDuplication(ListNode head) {
        ListNode newHead = new ListNode(-1);
        ListNode cur = head;
        ListNode tmp = newHead;
        while (cur != null) {
            if (cur.next != null && cur.val == cur.next.val) {
                while (cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                // 多走一步
                cur = cur.next;
            }else {
                tmp.next = cur;
                tmp = tmp.next;
                cur = cur.next;
            }
        }
        // 防止最后一个节点也是重复的
        tmp.next = null;
        return newHead.next;
    }
}

